from sys import exit
from os import listdir
from sys import argv, exit
from math import factorial, pow
from collections import defaultdict
from os.path import join, basename
from getpass import getuser

INT = 0
REAL = 1
PARTITION = 2

PATH = ""
        
def binomial(a, b):
    return 0 if b > a else factorial(a) / (factorial(b) * factorial(a - b))

class Partition:
    def __init__(self, filename):
        self._filename = join(PATH, filename)
        self.partition = None
        try:
            f = open(self._filename, "r")
        except IOError:
            print "Could not open file \"%s\"" % self._filename
            exit(1)
        else:
            self.partition = defaultdict(list)
            for v, k in [tuple(s.split()) for s in f.readlines()]:
                self.partition[k].append(v)    
            f.close()

    def calcCR(self, other):
        if self.partition is None or other is None:
            return 0.0
        top = bottom = 0
        totalSum = sumA = sumB = 0
        lastPart = 0

        for clusterA in self.partition.values():
            sumA += binomial(len(clusterA), 2)
            sumB = 0
            for clusterB in other.partition.values():
                sumB += binomial(len(clusterB), 2)
                elementsInBoth = sum([clusterB.count(obj) for obj in clusterA])
                totalSum += binomial(elementsInBoth, 2)

        elementsInA = sum([len(l) for l in self.partition.values()])
        lastPart = pow(binomial(elementsInA, 2), -1) * sumA * sumB
        top = totalSum - lastPart
        bottom = ((sumA + sumB)/2) - lastPart

        return top/bottom

    def __str__(self):
        return basename(self._filename)


class Array(list):
    def __init__(self, width, type_=None):
        self._width = width
        self.type_ = type_
        [self.append(None) for x in range(width)]

    def from_list(self, list_):
        for i in range(len(list_)):
            self[i] = list_[i]
            
    def size(self):
        return len([x for x in self if x is not None])

    def add(self, *args):
        i = 0
        for p in range(self._width):
            if i == len(args):
                break
            if self[p] is None:
                self[p] = args[i]
                i += 1
        return i

    def delete(self, *args):
        for (x,) in args:
            try:
                self[x] = None
            except IndexError:
                pass
            
    def hasStuff(self):
        for x in self:
            if x is not None:
                return True
        return False

    def mean(self):
        sum_ = 0.0
        count = 0
        for a in self:
            if type(a) in (float, int):
                sum_ += a
                count += 1
        return sum_ / count
                  
    def indexOfMax(self):
        return self.index(max(self))
        
    def __str__(self):
        fmt = lambda x: str(x)
        if self.type_ == REAL:
            fmt = lambda x: "%.4f" % x
        return "\t".join([fmt(v) if v is not None else "-" for v in self]) + "\n"


class Matrix(list):
    def __init__(self, width, height, type_=None):
        self._width = width
        self._height = height
        self.type_ = type_
        [self.append(Array(self._width, self.type_)) for x in range(self._height)]

    def size(self):
        return sum([a.size() for a in self])

    def add(self, *args):
        i = 0
        for p in range(self._height):
            i += self[p].add(*args[i:])
        return i
    
    def delete(self, *args):
        for (x, y) in args:
            self[x].delete((y,))

    def hasStuff(self):
        for a in self:
            if a.hasStuff():
                return True
        return False

    def mean(self):
        a = Array(self._height, REAL)
        a.from_list([x.mean() for x in self])
        return a
                
    def __str__(self):
        return "".join([str(a) for a in self])
        
def print_(*args):
    for arg in args:
        print arg,
    
def highestCR(array):
    return array.indexOfMax()

def calcMean(iterable):
    return iterable.mean()
    
def findSimilar(matrix, index, threshold):
    indexes = []
    line = matrix[index]
    for i in range(len(line)):
        if line[i] >= threshold:
            indexes.append([index, i])
    return indexes
    
def listfiles(dir_):
    try:
        return listdir(join(PATH, dir_))
    except:
        print "Could not list directory " + dir_
        exit(1)
    
def joinpath(p, f):
    return join(p, f)


def calcCR(a, b=None):
    if isinstance(a, Partition) and isinstance(b, Partition):
        return a.calcCR(b)
    elif isinstance(a, Partition) and isinstance(b, Array):
        calc = Array(len(b), REAL)
        for p in b:
            if p is not None:
                calc.add(a.calcCR(p))
        return calc
    elif b is None:
        calc = Matrix(len(a), len(a), REAL)
        for p in a:
            if p is not None:
                calc.add(*calcCR(p, a))
        return calc
